package StackOrQueue;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

class 滑动窗口最大值 {
    static class MyQueue{
        Deque<Integer> queue;
        public MyQueue(){
            queue = new LinkedList<>();
        }
        public void poll(int val){
            //弹出指定值时，若队列首部和val相等，才弹
            if(!queue.isEmpty() && val == queue.getFirst()){
                queue.pollFirst();
            }
        }

        public void add(int val){
            //向队列添加元素时，如果比队尾元素大，则弹出队尾
            while( !queue.isEmpty() && val > queue.getLast()){
                queue.pollLast();
            }
            queue.addLast(val);
        }
        //返回当前最大  ,队列是递减的，头部最大
        public int peek(){
            return queue.getFirst();
        }
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if(len==1){
            return nums;
        }
        int rLen = len - k + 1;  //结果的长度
        int[] res = new int[rLen];
        MyQueue queue = new MyQueue();
        //先将头几个放入
        for(int i=0;i<k;i++){
            queue.add(nums[i]);
        }
        int index = 0;
        res[index++] = queue.peek();

        for(int i=k;i<len;i++){
            //向后遍历，并移除昨边界，移进右边界
            queue.poll(nums[i-k]);
            queue.add(nums[i]);
            res[index++] = queue.peek();
        }
        return res;


    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3)));
    }
}
